
// 添加最少字符使字符串整体都是回文字符串


//代码思路还没走流程
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    string getPalindromel(string& str) {
        if (str.size() < 2) {
            return str;
        }
        vector<vector<int>> dp = getDP(str);
        vector<char> res(dp[0][str.size() - 1] + str.size());
        int i = 0;
        int j  = str.size() - 1;
        int resl = 0;
        int resr = res.size() - 1;
        while (i <= j) {
            if (str[i] == str[j]) {
                res[resl++] = str[i++];
                res[resr--] = str[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) {
                res[resl++] = str[j];
                res[resr--] = str[j--];
            } else {
                res[resl++] = str[i];
                res[resr--] = str[i++];
            }
        }

        for (auto X : res) {
            cout << X;
        }
        cout << endl;
        return string(res.begin(), res.end());
    }

private:
    vector<vector<int>> getDP(string& str) {
        vector<vector<int>> dp(str.size(), vector<int>(str.size()));
        for (int j = 1; j < str.size(); j++) {
            dp[j - 1][j] = str[j] == str[j - 1] ? 0 : 1;
            for (int i = j - 2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp;
    }
};

int main() {
    Solution solu;
    string str = "ABCD";
    cout << solu.getPalindromel(str) << endl;

    return 0;
}